package com.lishem.carl._10dp;

/**
 * https://leetcode.cn/problems/distinct-subsequences/description/
 * <p>
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
 * <p>
 * 输入：s = "rabbbit", t = "rabbit"
 * <p>
 * 输出：3
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "babgbag", t = "bag"
 * <p>
 * 输出：5
 */
public class _35LetCode115_不同的子序列 {

    public int numDistinct(String s, String t) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        int[][] dp = new int[sChars.length + 1][tChars.length + 1];
        for (int i = 0; i < sChars.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= sChars.length; i++) {
            for (int j = 1; j <= tChars.length; j++) {
                if (sChars[i - 1] == tChars[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[sChars.length][tChars.length];
    }

    public static void main(String[] args) {
        _35LetCode115_不同的子序列 sol = new _35LetCode115_不同的子序列();
        System.out.println(sol.numDistinct("rabbbit", "rabbit"));
        System.out.println(sol.numDistinct("babgbag", "bag"));
    }
}
